class Solution {
public:
    bool search(vector<int>& nums, int target) {
        int n = nums.size();
        int left = 0,right = n - 1;
        while(nums[0] == nums[right] && right > 0) right--;
        while(left <= right){
            int mid = (left + right) >> 1;
            if(nums[mid] >= nums[0]){
                left = mid + 1;
            }else{
                right = mid - 1;
            }
        }
        // cout << left <<' ' << right << endl;
        if(nums[0] > target){
           right = n - 1;
        }else{
            left = 0;
        }
        while(left <= right){
            int mid = (left + right) >> 1;
            if(nums[mid] > target){
                right = mid - 1;
            }else  if(nums[mid] < target){
                left = mid + 1;
            }else{
                return true;
            }
            // cout << left <<' ' << right << endl;
        }
        return false;
    }
};